import java.util.*;
import java.io.*;

public class Main 
{
    public static long cr;
    public static boolean alog[];
    public static void main(String[] args)  throws IOException, Exception 
    {
            genera();
            if (true==true)
            {
                throw new Exception("Fin del archivo de pruebas.");
            }
//        grafo g= new grafo(6, false);
//        g.insert(new Eje(0,3));
//        g.insert(new Eje(0,4));
//        g.insert(new Eje(4,5));
//        g.insert(new Eje(1,2));
//        g.insert(new Eje(2,5));
//        g.insert(new Eje(2,3));
//        g.insert(new Eje(2,4));
//        buscaRuta(g);
        File outputFile = new File("Tp2Ej2.out");
        File inputFile= new File("Tp2Ej2.in");
        FileReader inf = new FileReader(inputFile);
        FileWriter out = new FileWriter(outputFile);
        BufferedWriter salida = new BufferedWriter(out);
        BufferedReader entr= new BufferedReader(inf);
        String h;
        String resultado;
        h=entr.readLine();
        try
        {
            while (h!=null) //mientras no termine el archivo
            {
                int indice;
                indice=h.indexOf(" ");
                int n= Integer.valueOf(h.substring(0, indice)); //Cantidad de pueblos
                int m= Integer.valueOf(h.substring(indice+1, h.length())); // Acuerdos comerciales
                h=entr.readLine();
                if (n==0 && m==0)
                {
                    throw new Exception("Fin del archivo de pruebas.");
                }
                grafo ciudad = new grafo(n, false);
                int j=m;
                while (j>0)
                {
                    indice=h.indexOf(" ");
                    int p1= Integer.valueOf(h.substring(0, indice)); //Pueblo 1
                    int p2= Integer.valueOf(h.substring(indice+1, h.length())); //Pueblo 2
                    ciudad.insert(new Eje(p1-1, p2-1));
                    j--;
                    h=entr.readLine();
                }
                //calculo el tiempo inicial
                double tiempoInicio = System.currentTimeMillis();
                cr=0;
                List<Integer> camino = buscaRuta(ciudad);
                 //calculo el tiempo final
                double tiempoFinal = System.currentTimeMillis();
                double tiempo = tiempoFinal - tiempoInicio;
                if (camino.isEmpty())
                {
                    resultado="-1";
                }
                else
                {
                    resultado=camino.toString();
                }
                salida.write(resultado + "  -Tardó- " + String.valueOf(tiempo));
                salida.newLine();
                salida.flush();
            }
        }
        catch (Exception e)
        {
            if (!e.getMessage().equals("Fin del archivo de pruebas."))
            {
                System.out.print(e.toString());                
            }
        }
        finally
        {
            salida.close();
            entr.close();
        }
    }
    
    public static List<Integer> buscaRuta(grafo g)
    {
        int cantPueblos=g.V();
        boolean[][] TerminaEnNi = new boolean[cantPueblos][cantPueblos]; //Caminos que terminan en Ni
        boolean[][] TerminaEnNj = new boolean[cantPueblos][cantPueblos]; //Caminos que terminan en Nj
        // Java inicializa la matriz de booleanos con False
        int t=0;
        int x=0;
        int PuebloI;
        int PuebloJ;
        int ni,nj;
        boolean terminaEnI=true;
        boolean sePuede=true;
        boolean adjNiNj;
        List<Integer> ruta = new LinkedList<Integer>();
        //determino los caminos entre todos los Ni y Nj de tamaño x
        //Caso x = 1
    try
    {
        while (t<cantPueblos)
        {
            PuebloI=modulo((t+1),cantPueblos);
            if (g.Adyacente(t, PuebloI))
            {
                TerminaEnNi[t][PuebloI]=true;
                TerminaEnNj[t][PuebloI]=true;
                TerminaEnNi[t][t]=true;
                TerminaEnNj[t][t]=true;
            }
            t++;
        }
    }
    catch (Exception e)
    {
        System.out.print(e.toString() + " en determino los caminos entre todos los Ni y Nj de tamaño x=1");
    }
        //Casos x > 1
    try
    {
        x=2;
        while (x<cantPueblos)
        {
            t=0;
            while (t<cantPueblos)
            {
                ni=t;
                PuebloI=modulo((t+1),cantPueblos);
                nj=modulo((t+x),cantPueblos);
                PuebloJ=modulo((nj-1),cantPueblos);
                adjNiNj=g.Adyacente(ni, nj);
                // verifico si existe subruta que termine en ni
                if (TerminaEnNi[PuebloI][nj])
                {
                    if (g.Adyacente(ni, PuebloI))
                    {
                        TerminaEnNi[ni][nj]=true;
                    }
                }
                if (TerminaEnNj[PuebloI][nj])
                {
                    if (adjNiNj)
                    {
                            TerminaEnNi[ni][nj]=true;
                    }
                }
                //verifico si existe subruta que termine en nj
                if (TerminaEnNj[ni][PuebloJ])
                {
                    if (g.Adyacente(nj, PuebloJ))
                    {
                        TerminaEnNj[ni][nj]=true;
                    }
                }
                if (TerminaEnNi[ni][PuebloJ])
                {
                    if (adjNiNj)
                    {
                        TerminaEnNj[ni][nj]=true;
                    }
                }
                t++;
            }
            x++;
        }
    }
    catch (Exception e)
    {
        System.out.print(e.toString() + " en determino los caminos entre todos los Ni y Nj de tamaño x>1");
    }
        // Listas todas las rutas se verifica si existe una posible entre todas
    try
    {
        ni=0;
        nj=cantPueblos-1;
        t=0;
        while (t<cantPueblos)
        {
            sePuede=true;
            ni=t;
            nj=modulo((ni-1),cantPueblos);
            if (TerminaEnNi[ni][nj])
            {
                terminaEnI=true;
            }
            else if (TerminaEnNj[ni][nj])
            {
                terminaEnI=false;
            }
            else
            {
                sePuede=false;
            }
            while (sePuede && !(((nj-ni)==1) || ((nj==0) && (ni==cantPueblos-1))))
            {
                PuebloI=modulo((ni+1),cantPueblos);
                PuebloJ=modulo((nj-1),cantPueblos);
                adjNiNj=g.Adyacente(ni, nj);
                if (terminaEnI)
                {
                    ruta.add(ni+1);
                    if (TerminaEnNi[PuebloI][nj] && g.Adyacente(ni, PuebloI))
                    {
                        ni=PuebloI;
                    }
                    else if (TerminaEnNj[PuebloI][nj] && adjNiNj)
                    {
                        terminaEnI=false;
                        ni=PuebloI;
                    }
                    else
                    {
                        sePuede=false;
                    }
                }
                else
                {
                    ruta.add(nj+1);
                    if (TerminaEnNj[nj][PuebloJ] && g.Adyacente(nj, PuebloJ))
                    {
                        nj=PuebloJ;
                    }
                    else if (TerminaEnNi[ni][PuebloJ] && adjNiNj)
                    {
                        terminaEnI=true;
                        nj=PuebloJ;
                    }
                    else
                    {
                        sePuede=false;
                    }
                }
            }
            if (sePuede)
            {
                ruta.add(ni+1);
                ruta.add(nj+1);
                return ruta;
            }
            t++;
            ruta.clear();
        }
    }
    catch (Exception e)
    {
        System.out.print(e.toString() + " en verificacion de existencia de ruta");
    }
        ruta.clear();
        return ruta;
    }   
    
    public static int modulo(int a, int b)
    {
        if (a<0)
        {
            return b+a;
        }
        else
        {
            return a%b;
        }
    }
    
    public static void generaInstancias(int i)
    {

    }
        
    public static void genera() throws IOException
    {
        int pueb=10;
        int increm=10;
        Random aleatorio = new Random();
        int subIncrem= aleatorio.nextInt(increm);
        File outputFile = new File("Tp2Ej2"+String.valueOf(pueb)+"-"+String.valueOf(pueb+(pueb*increm))+".in");
        FileWriter out = new FileWriter(outputFile);
        BufferedWriter salida = new BufferedWriter(out);
        int total=(pueb*increm);
        int cantPueblos=pueb;
        int cantAcuerdos=0;
        int pueblo1;
        int pueblo2;
        try
        {
            while (cantPueblos<total)
            {
                int ran=facto(cantPueblos);
                if (ran<0) ran=-ran;
                if (ran==0) ran=cantPueblos;
                cantAcuerdos = aleatorio.nextInt(ran); 
                cantAcuerdos = ( cantAcuerdos< 1 ) ? -cantAcuerdos : cantAcuerdos;
                salida.write(String.valueOf(cantPueblos) + " "+ String.valueOf(cantAcuerdos));
                salida.newLine();
                grafo g= new grafo(cantPueblos, false);
                try
                {
                    while (cantAcuerdos>0)
                    {
                            pueblo1=1;
                            pueblo2=1;
                            boolean s=true;
                            while (s)
                            {
                                pueblo1=aleatorio.nextInt(cantPueblos)+1;
                                pueblo2=pueblo1;
                                while (pueblo1==pueblo2)
                                {
                                    pueblo2=aleatorio.nextInt(cantPueblos)+1;
                                }
                                if (!g.Adyacente(pueblo1, pueblo2))
                                {
                                    g.insert(new Eje(pueblo1, pueblo2));
                                    s=false;
                                }
                            }
                            salida.write(String.valueOf(pueblo1) + " " + String.valueOf(pueblo2));
                            salida.newLine();
                            cantAcuerdos--;
                            salida.flush();
                    }
                }
                catch (Exception e)
                {
                    System.out.print(e.getMessage());
                }
                cantPueblos=cantPueblos+increm+subIncrem;
            }
        }
        finally
        {
                    salida.write("0 0");
                    salida.close();
        }
    }
    public static int facto(int n)
    {
        int i=n;
        int j=1;
        try
        {
            while (i>0)
            {
                j=j*i;
                i--;
            }
            if (j>0)
            {
                return j;                
            }
            else
            {
                return -j;
            }   
        }
        catch (Exception ex)
        {
            return n;
        }
    }
}


